/*
 * @Author: Starfish_DL
 * @Date: 2020-11-09 20:06:29
 * @LastEditors: Starfish_DL
 * @LastEditTime: 2020-11-10 01:00:26
 * @CurrentVersion: 1.0
 * @Description: 
 */

#include <iostream>
#include "CStack.h"
#include "CLinkTree.h"
using namespace std;

CSqBinTree::CSqBinTree(string str)
{
    this->length = str.length();
    try
    {
        for (int i = 0; i < this->length; i++)
        {
            this->data[i] = str[i];
        }
    }
    catch (const std::exception &e)
    {
        std::cerr << e.what() << '\n';
    }
}

CSqBinTree::~CSqBinTree()
{
}

CNode::CNode(char a)
{
    this->data = a;
    this->leftchild = nullptr;
    this->rightchild = nullptr;
}

CNode::CNode(char a, CNode *l, CNode *r)
{
    /**
     * @author: Starfish_DL
     * @description:第二个参数是左儿子，第三个参数是右儿子！
     * @param {char a,CNode l,CNode r}
     * @return {*}
     */
    this->data = a;
    this->leftchild = l;
    this->rightchild = r;
}

CNode::~CNode()
{
}

CLinkTree::CLinkTree(string str)
{
    int k = 0, top = -1;
    CNode *stack[MAXSIZE], *p;
    for (int i = 0; i < str.length(); i++)
    {
        switch (str[i])
        {
        case '(':
            top++;
            stack[top] = p;
            k = 1;
            break;
        case ')':
            top--;
            break;
        case ',':
            k = 2;
            break;
        default:
            p = new CNode(str[i]);
            if (this->head == nullptr)
            {
                this->head = p;
            }
            else
            {
                switch (k)
                {
                case 1:
                    stack[top]->leftchild = p;
                    break;
                case 2:
                    stack[top]->rightchild = p;
                    break;
                }
            }
            break;
        }
    }
}

CLinkTree::CLinkTree(CSqBinTree t)
{
    CreateTree(this->head, 1, t);
}

int CLinkTree::Height()
{
    return height(this->head);
}

void CLinkTree::DispTree()
{
    dispTree(this->head);
}

CLinkTree::~CLinkTree()
{
    DestroyTree(this->head);
}

void CreateTree(CNode *n, int i, CSqBinTree tree)
{
    if (i >= tree.length || tree.data[i - 1] == '#')
    {
        n = nullptr;
    }
    else
    {
        n = new CNode(tree.data[i - 1]);
        CreateTree(n->leftchild, i * 2, tree);
        CreateTree(n->rightchild, i * 2 + 1, tree);
    }
    return;
}

int height(CNode *n)
{
    if (n->leftchild == nullptr && n->rightchild == nullptr)
    {
        return 1;
    }
    else
    {
        if (height(n->leftchild) > height(n->rightchild))
        {
            return height(n->leftchild) + 1;
        }
        else
        {
            return height(n->rightchild) + 1;
        }
    }
}

void DestroyTree(CNode *n)
{
    if (n != nullptr)
    {
        DestroyTree(n->leftchild);
        DestroyTree(n->rightchild);
        delete n;
    }
}

void dispTree(CNode *n)
{
    if (n != nullptr)
    {
        cout << n->data;
        if (n->leftchild != nullptr || n->rightchild != nullptr)
        {
            cout << "(";
            dispTree(n->leftchild);
            if (n->rightchild != nullptr)
            {
                cout << ",";
            }
            dispTree(n->rightchild);
            cout << ")";
        }
    }
}